package com.kevinkk.stackandqueue;

import java.util.Deque;
import java.util.ArrayDeque;

/**
 * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 *
 * 用栈实现队列时，需要用到两个栈
 * 用队列实现栈时，只需要一个队列，有点类似贪吃蛇，做一个循环的操作即可找到队尾的元素
 */

public class ImplementStackUsingQueues {
    class MyStack {
        Deque<Integer> que = new ArrayDeque<>();

        public MyStack() {
        }

        public void push(int x) {
            que.addLast(x);
        }

        public int pop() {
            for (int i = 0; i < que.size() - 1; i++)
                que.addLast(que.removeFirst());
            return que.removeFirst();
        }

        public int top() {
            int res = pop();
            que.addLast(res);
            return res;
        }

        public boolean empty() {
            return que.isEmpty();
        }
    }
}
